package Algorithm.sort;

/**
 * @Desc: 双端扫描交换排序 Double-End Scan and Swap
 * @author: cww
 * @DateTime: 2020-04-12 23:59
 */

public class DeScanSwapSort {

    public static void main(String[] args) {
        int[] items = new int[]{4,5,6,6,2,1};
        deScanSwapSort1(items,0,5);
        System.out.println(items);
    }

    /**
     * 1.单轴快排-双端扫描交换方式-图解.png
     * @param items
     * @param start
     * @param end
     */
    public static void deScanSwapSort(int[] items, int start, int end) {
        if (start<end){
            int head = items[start];
            int i = start+1,j=end;
            while (i<=j){// 要用等于主要是两个游标相交
                while (i<=j && items[i]<head) i++;// 如果左游标小于head则直接将游标右移
                // 如果右游标值>= head 则直接将游标左移,
                // 当i已经过了分界线后，j会继续左移，直到找到比head小的点，再跳出循环，
                // 将head 与j交换，才能达到j左边都是小于head
                while (i<=j && items[j]>=head) j--;
                if (i<=j) swap(items,i,j);// 这里还要做个<=判断，因为可能最后要结束了
            }
            swap(items,start,j);
            deScanSwapSort(items, start,j-1);
            deScanSwapSort(items, j+1,end);
        }
    }

    public static void swap(int[] item, int p, int q){
        int temp = item[p];
        item[p] = item[q];
        item[q] = temp;
    }

    /**
     * 练习
     * @param items
     * @param start
     * @param end
     */
    public static void deScanSwapSort1(int[] items, int start, int end){
        if(start<end){
            int head = items[start];
            int i = start+1,j=end;
            while(i<=j){
                while(i<=j&&items[i]<head) i++;
                while(i<=j&&items[j]>=head)j--;
                if(i<=j){
                    swap(items,i,j);
                }
            }
            swap(items,start,j);
            deScanSwapSort1(items,start,j-1);
            deScanSwapSort1(items,j+1,end);        }
    }
}
